{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Good Ways to Split a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numSplits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串的好分割数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;，一个分割被称为 「好分割」&nbsp;当它满足：将&nbsp;<code>s</code>&nbsp;分割成 2 个字符串&nbsp;<code>p</code> 和&nbsp;<code>q</code>&nbsp;，它们连接起来等于&nbsp;<code>s</code>&nbsp;且 <code>p</code>&nbsp;和 <code>q</code>&nbsp;中不同字符的数目相同。</p>\n",
    "\n",
    "<p>请你返回 <code>s</code>&nbsp;中好分割的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;aacaba&quot;\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>总共有 5 种分割字符串 <code>&quot;aacaba&quot;</code> 的方法，其中 2 种是好分割。\n",
    "(&quot;a&quot;, &quot;acaba&quot;) 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。\n",
    "(&quot;aa&quot;, &quot;caba&quot;) 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。\n",
    "(&quot;aac&quot;, &quot;aba&quot;) 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。\n",
    "(&quot;aaca&quot;, &quot;ba&quot;) 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。\n",
    "(&quot;aacab&quot;, &quot;a&quot;) 左边字符串和右边字符串分别包含 3 个和 1 个不同的字符。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;abcd&quot;\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>好分割为将字符串分割成 (&quot;ab&quot;, &quot;cd&quot;) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;aaaaa&quot;\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>所有分割都是好分割。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;acbadbaada&quot;\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母。</li>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10^5</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-good-ways-to-split-a-string](https://leetcode.cn/problems/number-of-good-ways-to-split-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-good-ways-to-split-a-string](https://leetcode.cn/problems/number-of-good-ways-to-split-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aacaba\"', '\"abcd\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        d=[0]*123\n",
    "        f=Counter(s) \n",
    "        w=len(f)\n",
    "        b=a=0\n",
    "        for c in s:\n",
    "            if f[c]==1:\n",
    "                w-=1\n",
    "            else:\n",
    "                f[c]-=1\n",
    "\n",
    "            if d[ord(c)]==0:\n",
    "                b+=1\n",
    "                d[ord(c)]=1\n",
    "\n",
    "            a+=b==w\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        d=[0]*123\n",
    "        f=Counter(s) \n",
    "        b=a=0\n",
    "        for c in s:\n",
    "            if f[c]==1:\n",
    "                del f[c]\n",
    "            else:\n",
    "                f[c]-=1\n",
    "\n",
    "            if d[ord(c)]==0:\n",
    "                b+=1\n",
    "                d[ord(c)]=1\n",
    "                \n",
    "            if b==len(f):\n",
    "                a+=1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        left, right = Counter(), Counter(s)\n",
    "        leftCnt, rightCnt = len(left), len(right)\n",
    "        for i in range(0, len(s)):\n",
    "            if s[i] not in left:\n",
    "                left[s[i]] = 1\n",
    "                leftCnt += 1\n",
    "            if right[s[i]] > 0:\n",
    "                right[s[i]] -= 1\n",
    "            if right[s[i]] == 0:\n",
    "                rightCnt -= 1\n",
    "            if leftCnt == rightCnt:\n",
    "            \tans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        d=[0]*123\n",
    "        f=Counter(s) \n",
    "        w=len(f)\n",
    "        b=a=0\n",
    "        for c in s:\n",
    "            if f[c]==1:\n",
    "                w-=1\n",
    "            else:\n",
    "                f[c]-=1\n",
    "            t=ord(c)\n",
    "            if d[t]==0:\n",
    "                b+=1\n",
    "                d[t]=1\n",
    "            a+=b==w\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        left = set()\n",
    "        right = set(s)\n",
    "        count = collections.defaultdict(int)\n",
    "        for i in range(len(s)):\n",
    "            count[s[i]] += 1\n",
    "            right.add(s[i])\n",
    "        # print(count)\n",
    "        for i in range(len(s) - 1):\n",
    "            left.add(s[i])\n",
    "            count[s[i]] -= 1\n",
    "            if count[s[i]] < 1:\n",
    "                right.discard(s[i])\n",
    "            # print(count, s[:i + 1], s[i+1:], len(left), len(right))\n",
    "            if len(left) == len(right):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        d=[0]*123\n",
    "        f=Counter(s) \n",
    "        w=len(f)\n",
    "        b=a=0\n",
    "        for c in s:\n",
    "            if f[c]==1:\n",
    "                w-=1\n",
    "            else:\n",
    "                f[c]-=1\n",
    "            t=ord(c)\n",
    "            if d[t]==0:\n",
    "                b+=1\n",
    "                d[t]=1\n",
    "            a+=b==w\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        sc = collections.Counter(s)\n",
    "        r = len(sc) # 不同字符个数\n",
    "        left = {}\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            if c in left:\n",
    "                left[c] += 1\n",
    "            else:\n",
    "                left[c] = 1\n",
    "            if left[c] == sc[c]:\n",
    "                r -= 1 # 当前字符已经全部出现\n",
    "            if len(left) == r:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        d={}\n",
    "        f=Counter(s) \n",
    "        a=0\n",
    "        for c in s:\n",
    "            if f[c]==1:\n",
    "                del f[c]\n",
    "            else:\n",
    "                f[c]-=1\n",
    "            d[c]=1\n",
    "            if len(d)==len(f):\n",
    "                a+=1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        d=[0]*123\n",
    "        f=Counter(s) \n",
    "        w=len(f)\n",
    "        b=a=0\n",
    "        for c in s:\n",
    "            if f[c]==1:\n",
    "                w-=1\n",
    "            else:\n",
    "                f[c]-=1\n",
    "            t=ord(c)\n",
    "            if d[t]==0:\n",
    "                b+=1\n",
    "                d[t]=1\n",
    "            a+=b==w\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        d=[0]*123\n",
    "        f=Counter(s) \n",
    "        w=len(f)\n",
    "        b=a=0\n",
    "        for c in s:\n",
    "            if f[c]==1:\n",
    "                w-=1\n",
    "            else:\n",
    "                f[c]-=1\n",
    "\n",
    "            if d[ord(c)]==0:\n",
    "                b+=1\n",
    "                d[ord(c)]=1\n",
    "\n",
    "            if b==w:a+=1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        right = Counter(s)\n",
    "        left = set()\n",
    "        ans = 0\n",
    "        for c in s[:-1]:\n",
    "            left.add(c)\n",
    "            right[c] -= 1\n",
    "            if right[c] == 0:\n",
    "                del right[c]\n",
    "            if len(left) == len(right):\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        m1 = [0] * 26\n",
    "        m2 = [0] * 26\n",
    "        ret = f1 = f2 = 0\n",
    "        for c in s:\n",
    "            f1 += m1[ord(c) - 97] == 0\n",
    "            m1[ord(c) - 97] += 1\n",
    "        for c in s:\n",
    "            m1[ord(c) - 97] -= 1\n",
    "            f1 -= m1[ord(c) - 97] == 0\n",
    "            f2 += m2[ord(c) - 97] == 0\n",
    "            m2[ord(c) - 97] += 1\n",
    "            ret += f1 == f2\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        cntA = Counter()\n",
    "        cntB = Counter()\n",
    "        res = 0\n",
    "\n",
    "        for i, x in enumerate(s):\n",
    "            cntB[x] += 1\n",
    "        \n",
    "        for i, x in enumerate(s):\n",
    "            cntA[x] += 1\n",
    "            if cntB[x]:\n",
    "                cntB[x] -= 1\n",
    "            if cntB[x] == 0:\n",
    "                del cntB[x]\n",
    "            if len(cntA) == len(cntB):\n",
    "                res += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        retravel, travel = [0] * 26, [0] * 26\n",
    "        qcount, pcount, ans = 0, 0, 0\n",
    "        # 第一次遍历，用travel统计每个字母出现的次数\n",
    "        for i in s:\n",
    "            travel[ord(i) - ord('a')] += 1\n",
    "            # 当一个新字母出现时，增加一次不同字母数\n",
    "            if travel[ord(i) - ord('a')] == 1:\n",
    "                qcount += 1\n",
    "        # 第二次遍历，用retravel统计当前每个字母出现的次数\n",
    "        for i in s:\n",
    "            retravel[ord(i) - ord('a')] += 1\n",
    "            # 当一个新字母出现时，增加一次不同字母数\n",
    "            if retravel[ord(i) - ord('a')] == 1:\n",
    "                pcount += 1\n",
    "            # 如果当前遍历到某个字母出现的次数是整个字符串该字母的总次数，剩下右部分不会再有该字母\n",
    "            # 即右部分的不同字母数少一\n",
    "            if retravel[ord(i) - ord('a')] == travel[ord(i) - ord('a')]:\n",
    "                qcount -= 1\n",
    "            # 当左右（p和q）部分不同字母数相等时，则为一次好分割\n",
    "            if pcount == qcount:\n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        c1 = Counter(s)\n",
    "        c2 = Counter()\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            c1[s[i]] -= 1\n",
    "            if c1[s[i]] == 0:\n",
    "                c1.pop(s[i])\n",
    "            c2[s[i]] += 1\n",
    "            if len(c1) == len(c2):\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        pre=[0]*26\n",
    "        suf=[0]*26\n",
    "        for ch in s:\n",
    "            suf[ord(ch)-97]+=1\n",
    "        ans=0\n",
    "        for i in range(1,n):\n",
    "            pre[ord(s[i-1])-97]+=1\n",
    "            suf[ord(s[i-1])-97]-=1\n",
    "            a,b=sum(j>0 for j in pre),sum(k>0 for k in suf)\n",
    "            if a==b: ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        cntback=Counter(s)\n",
    "        nback=len(cntback.keys())\n",
    "        cntfront=set()\n",
    "        nfront=0\n",
    "        ans=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in cntfront:\n",
    "                nfront+=1\n",
    "            cntfront.add(s[i])\n",
    "            cntback[s[i]]-=1\n",
    "            if cntback[s[i]]==0:\n",
    "                nback-=1\n",
    "            if nback==nfront:\n",
    "                ans+=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        pre=[0]*26\n",
    "        suf=[0]*26\n",
    "        for ch in s:\n",
    "            suf[ord(ch)-97]+=1\n",
    "        ans=0\n",
    "        for i in range(1,n):\n",
    "            pre[ord(s[i-1])-97]+=1\n",
    "            suf[ord(s[i-1])-97]-=1\n",
    "            a,b=sum(j>0 for j in pre),sum(k>0 for k in suf)\n",
    "            if a==b: ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        retravel, travel = [0] * 26, [0] * 26\n",
    "        qcount, pcount, ans = 0, 0, 0\n",
    "        # 第一次遍历，用travel统计每个字母出现的次数\n",
    "        for i in s:\n",
    "            travel[ord(i) - ord('a')] += 1\n",
    "            # 当一个新字母出现时，增加一次不同字母数\n",
    "            if travel[ord(i) - ord('a')] == 1:\n",
    "                qcount += 1\n",
    "        # 第二次遍历，用retravel统计当前每个字母出现的次数\n",
    "        for i in s:\n",
    "            retravel[ord(i) - ord('a')] += 1\n",
    "            # 当一个新字母出现时，增加一次不同字母数\n",
    "            if retravel[ord(i) - ord('a')] == 1:\n",
    "                pcount += 1\n",
    "            # 如果当前遍历到某个字母出现的次数是整个字符串该字母的总次数，剩下右部分不会再有该字母\n",
    "            # 即右部分的不同字母数少一\n",
    "            if retravel[ord(i) - ord('a')] == travel[ord(i) - ord('a')]:\n",
    "                qcount -= 1\n",
    "            # 当左右（p和q）部分不同字母数相等时，则为一次好分割\n",
    "            if pcount == qcount:\n",
    "                ans += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        d=[0]*123\n",
    "        f=Counter(s) \n",
    "        w=len(f)\n",
    "        b=a=0\n",
    "        for c in s:\n",
    "            if f[c]==1:\n",
    "                w-=1\n",
    "            else:\n",
    "                f[c]-=1\n",
    "            t=ord(c)\n",
    "            if d[t]==0:\n",
    "                b+=1\n",
    "                d[t]=1\n",
    "\n",
    "            a+=b==w\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        count_right = collections.Counter(s)\n",
    "        count_left = collections.defaultdict(int)\n",
    "        left, right = len(count_left), len(count_right)\n",
    "        for ch in s:\n",
    "            if ch not in count_left:\n",
    "                left += 1\n",
    "\n",
    "            count_left[ch] += 1\n",
    "            count_right[ch] -= 1\n",
    "\n",
    "            if count_right[ch] == 0:\n",
    "                right -= 1\n",
    "            \n",
    "            if left == right:\n",
    "                ans += 1\n",
    "                \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        p = [0] * 26\n",
    "        q = [0] * 26\n",
    "        for x in s:\n",
    "            q[ord(x) - ord(\"a\")] += 1\n",
    "        for y in s:\n",
    "            p[ord(y) - ord(\"a\")] += 1\n",
    "            q[ord(y) - ord(\"a\")] -= 1\n",
    "            if p.count(0) > q.count(0):\n",
    "                continue\n",
    "            if p.count(0) == q.count(0):\n",
    "                ans += 1\n",
    "                continue\n",
    "            break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        cp = Counter()\n",
    "        cq = Counter(s)\n",
    "        for x in s:\n",
    "            cp[x] += 1\n",
    "            cq[x] -= 1\n",
    "            if cq[x] == 0:\n",
    "                del cq[x]\n",
    "            if len(cp) == len(cq):\n",
    "                ans += 1\n",
    "\n",
    "        return ans            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        # 一个哈希表记录左串的情况一个记录右串的情况\n",
    "        left = defaultdict(int)\n",
    "        right = Counter(s)\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if len(left) == len(right):\n",
    "                ans += 1\n",
    "            left[s[i]] += 1\n",
    "            if right[s[i]] == 1:\n",
    "                del right[s[i]]\n",
    "            else:\n",
    "                right[s[i]] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        prefix = [0] * 26\n",
    "        pre = flag = cur = cnt = 0\n",
    "        for ch in s:\n",
    "            prefix[ord(ch) - ord(\"a\")] += 1\n",
    "        \n",
    "        for i in range(26):\n",
    "            if prefix[i]:   flag += 1\n",
    "        \n",
    "        for ch in s:\n",
    "            prefix[ord(ch) - ord(\"a\")] -= 1\n",
    "            if prefix[ord(ch) - ord(\"a\")] == 0:\n",
    "                flag -= 1\n",
    "            if pre & (1 << (ord(ch) - ord(\"a\"))) == 0:\n",
    "                pre |= 1 << (ord(ch) - ord(\"a\"))\n",
    "                cur += 1\n",
    "            if cur == flag:\n",
    "                cnt += 1\n",
    "            elif cur > flag:\n",
    "                break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def numSplits(self, s: str) -> int:\n",
    "    count, res = {}, 0\n",
    "    for ch in s:\n",
    "      count[ch] = count.get(ch, 0) + 1\n",
    "    if len(count) == 1:\n",
    "      return len(s) - 1\n",
    "    tmp, target = {}, len(count) // 2\n",
    "    for i in range(0, len(s) - 1):\n",
    "      ch = s[i]\n",
    "      tmp[ch] = tmp.get(ch, 0) + 1\n",
    "      count[ch] -= 1\n",
    "      if count[ch] == 0:\n",
    "        del count[ch]\n",
    "      ts, cs  = len(tmp), len(count)\n",
    "      if ts == cs:\n",
    "        res += 1\n",
    "      elif ts > cs:\n",
    "        break\n",
    "    return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        p, q = [0] * 26, [0] * 26\n",
    "        pcount = qcount = 0\n",
    "        res = 0\n",
    "        for c in s:\n",
    "            q[ord(c) - ord('a')] += 1\n",
    "            if q[ord(c) - ord('a')] == 1:\n",
    "                qcount += 1\n",
    "        for c in s:\n",
    "            p[ord(c) - ord('a')] += 1\n",
    "            if p[ord(c) - ord('a')] == 1:\n",
    "                pcount += 1\n",
    "            if p[ord(c) - ord('a')] == q[ord(c) - ord('a')]:\n",
    "                qcount -= 1\n",
    "            if pcount == qcount:\n",
    "                res += 1\n",
    "            if pcount > qcount:\n",
    "                return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        pre=[0]*26\n",
    "        suf=[0]*26\n",
    "        for ch in s:\n",
    "            suf[ord(ch)-97]+=1\n",
    "        ans,p,q=0,0,sum(k>0 for k in suf)\n",
    "        for i in range(1,n):\n",
    "            pre[ord(s[i-1])-97]+=1\n",
    "            if pre[ord(s[i-1])-97]==1: p+=1\n",
    "            suf[ord(s[i-1])-97]-=1\n",
    "            if suf[ord(s[i-1])-97]==0: q-=1\n",
    "            if p==q: ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s1, s2 = Counter(), Counter(s)\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s):\n",
    "            s1[c] += 1\n",
    "            s2[c] -= 1\n",
    "            if s2[c] == 0: del s2[c]\n",
    "            if len(s1) == len(s2):\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        cnt = Counter(s)\n",
    "        right = len(cnt)\n",
    "        left = set()\n",
    "        ans = 0\n",
    "        for c in s[:-1]:\n",
    "            left.add(c)\n",
    "            cnt[c] -= 1\n",
    "            if cnt[c] == 0:\n",
    "                right -= 1\n",
    "            if len(left) == right:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        c1 = Counter(s)\n",
    "        n = len(s)\n",
    "        c2 = Counter()\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            c1[s[i]] -= 1\n",
    "            if c1[s[i]] == 0:\n",
    "                c1.pop(s[i])\n",
    "            c2[s[i]] += 1\n",
    "            if len(c1) == len(c2):\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        # 简单粗暴的方法\n",
    "        # res = 0\n",
    "        # for i in range(len(s)):\n",
    "        #     if len(set(s[:i])) == len(set(s[i:])):\n",
    "        #         res += 1\n",
    "        # return res\n",
    "        # 暴力方法会超时，需要优化\n",
    "        # 哈希表优化，可以通过两次遍历，一次统计每一个位置有几个不同的字母\n",
    "        # 在从右边倒序统计有几个不同的字母\n",
    "        left = defaultdict(int)\n",
    "        right = Counter(s)\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            if len(left) == len(right):\n",
    "                ans += 1\n",
    "            left[s[i]] += 1\n",
    "            if right[s[i]] == 1:\n",
    "                del right[s[i]]\n",
    "            else:\n",
    "                right[s[i]] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        cntback=Counter(s)\n",
    "        nback=len(cntback.keys())\n",
    "        cntfront=Counter()\n",
    "        nfront=0\n",
    "        ans=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in cntfront:\n",
    "                nfront+=1\n",
    "            cntfront[s[i]]+=1\n",
    "            cntback[s[i]]-=1\n",
    "            if cntback[s[i]]==0:\n",
    "                nback-=1\n",
    "            if nback==nfront:\n",
    "                ans+=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        #枚举+计数+常数级优化\n",
    "        #本质是O(n)时间复杂度的\n",
    "        n=len(s)\n",
    "        pre=[0]*26\n",
    "        suf=[0]*26\n",
    "        for ch in s:\n",
    "            suf[ord(ch)-97]+=1\n",
    "        ans,p,q=0,0,sum(k>0 for k in suf)\n",
    "        for i in range(1,n):\n",
    "            pre[ord(s[i-1])-97]+=1\n",
    "            if pre[ord(s[i-1])-97]==1: p+=1\n",
    "            suf[ord(s[i-1])-97]-=1\n",
    "            if suf[ord(s[i-1])-97]==0: q-=1\n",
    "            if p==q: ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        p = [0] * 26\n",
    "        q = [0] * 26\n",
    "        for x in s:\n",
    "            q[ord(x) - ord(\"a\")] += 1\n",
    "        for y in s:\n",
    "            p[ord(y) - ord(\"a\")] += 1\n",
    "            q[ord(y) - ord(\"a\")] -= 1\n",
    "            if p.count(0) == q.count(0):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        def cal(l):\n",
    "            return sum(1 if i > 0 else 0 for i in l)\n",
    "        \n",
    "        c1, c2 = [0] * 26, [0] * 26\n",
    "        for c in s:\n",
    "            c2[ord(c)-97] += 1\n",
    "            \n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            c1[ord(c)-97] += 1\n",
    "            c2[ord(c)-97] -= 1\n",
    "            if cal(c1) == cal(c2):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        s1_set = set()\n",
    "        s2_set = set()\n",
    "        ret = 0\n",
    "        s_set = set()\n",
    "        t = len(set(s))\n",
    "        for i in range(1,length):\n",
    "            for j in s[:i]:\n",
    "                s1_set.add(j)\n",
    "                if len(s1_set) == t:\n",
    "                    break\n",
    "            for k in s[i:]:\n",
    "                s2_set.add(k)\n",
    "                if len(s2_set) == t:\n",
    "                    break\n",
    "            if len(s1_set) == len(s2_set):\n",
    "                ret+=1\n",
    "            s1_set.clear()\n",
    "            s2_set.clear()\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        p = [0] * 26\n",
    "        q = [0] * 26\n",
    "        for x in s:\n",
    "            q[ord(x) - ord(\"a\")] += 1\n",
    "        for y in s:\n",
    "            p[ord(y) - ord(\"a\")] += 1\n",
    "            q[ord(y) - ord(\"a\")] -= 1\n",
    "            if p.count(0) < q.count(0):\n",
    "                break\n",
    "            if p.count(0) == q.count(0):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        right_dict = dict()\n",
    "        for char in s:\n",
    "            if char not in right_dict.keys():\n",
    "                right_dict[char] = 1\n",
    "            else:\n",
    "                right_dict[char] += 1\n",
    "        left_dict = {}\n",
    "        result = 0\n",
    "        for char in s[:-1]:\n",
    "            if char not in left_dict.keys():\n",
    "                left_dict[char] = 1\n",
    "            else:\n",
    "                left_dict[char] += 1\n",
    "            right_dict[char] -= 1\n",
    "            if right_dict[char] == 0:\n",
    "                del right_dict[char]\n",
    "            if len(left_dict.keys()) == len(right_dict.keys()):\n",
    "                result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        prefix = [0] * 26\n",
    "        pre = flag = cur = cnt = 0\n",
    "        for ch in s:\n",
    "            prefix[ord(ch) - ord(\"a\")] += 1\n",
    "        \n",
    "        for i in range(26):\n",
    "            if prefix[i]:   flag += 1\n",
    "        \n",
    "        for ch in s:\n",
    "            prefix[ord(ch) - ord(\"a\")] -= 1\n",
    "            if prefix[ord(ch) - ord(\"a\")] == 0:\n",
    "                flag -= 1\n",
    "            if pre & (1 << (ord(ch) - ord(\"a\"))) == 0:\n",
    "                pre |= 1 << (ord(ch) - ord(\"a\"))\n",
    "                cur += 1\n",
    "            if cur == flag:\n",
    "                cnt += 1\n",
    "            elif cur > flag:\n",
    "                break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        # we create two dicrionaries. One to recods the letters\n",
    "        # in the left sub-string, one records the right string\n",
    "        left_dict  = dict()\n",
    "        right_dict = collections.Counter(s)\n",
    "\n",
    "        len_left_dict   = 0 \n",
    "        len_right_dict  = len(right_dict)\n",
    "\n",
    "        # count the good splits\n",
    "        cnt = 0 \n",
    "        # loop over all letters. \n",
    "        for i in range(len(s)):\n",
    "            # count the frequency of the letter in the left_dic\n",
    "            if s[i] not in left_dict:\n",
    "                left_dict[s[i]] = 1\n",
    "                len_left_dict += 1\n",
    "            else:\n",
    "                left_dict[s[i]] += 1 \n",
    "            \n",
    "            # substract the letter from the right dictionary\n",
    "            if right_dict[s[i]] >1 :\n",
    "                right_dict[s[i]] -= 1\n",
    "            else:\n",
    "                right_dict.pop(s[i])\n",
    "                len_right_dict -= 1\n",
    "            \n",
    "            # check if they contain the same number of diff letters\n",
    "            if len_left_dict == len_right_dict:\n",
    "                cnt += 1\n",
    "\n",
    "        return cnt\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        dict1 = defaultdict(int)\n",
    "        en_set_r = set()\n",
    "        en_set_l = set()\n",
    "        for i in s:\n",
    "            if dict1[i] == 0:\n",
    "                en_set_r.add(i)\n",
    "            dict1[i] += 1\n",
    "        res = 0\n",
    "        for i in s:\n",
    "            dict1[i] -= 1\n",
    "            if i not in en_set_l:\n",
    "                en_set_l.add(i)\n",
    "            if dict1[i] == 0:\n",
    "                en_set_r.remove(i)\n",
    "            if len(en_set_l) == len(en_set_r):\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        prev=1\n",
    "        after=len(set(s[1:]))\n",
    "        res=0\n",
    "        if prev==after:\n",
    "            res+=1\n",
    "        for i in range(2,len(s)):\n",
    "            if s[i-1] not in s[:i-1]:\n",
    "                prev+=+1\n",
    "            if s[i-1] not in s[i:]:\n",
    "                after-=1\n",
    "            if prev==after:\n",
    "                res+=1\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numSplits(self, s: str) -> int:\r\n",
    "        cnt = Counter(s)\r\n",
    "        cnt2 = Counter()\r\n",
    "        ans = 0\r\n",
    "        for k in s:\r\n",
    "            cnt[k] -= 1\r\n",
    "            cnt2[k] += 1\r\n",
    "            if cnt[k] == 0:\r\n",
    "                cnt.pop(k)\r\n",
    "            if len(cnt2) == len(cnt): \r\n",
    "                ans += 1\r\n",
    "        return ans    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        cntR = Counter(s)\n",
    "        cntL = Counter()\n",
    "        l, r = 0, len(cntR)\n",
    "        ans = 0\n",
    "        for x in s:\n",
    "            cntL[x] += 1\n",
    "            cntR[x] -= 1 \n",
    "            if cntR[x] == 0:\n",
    "                r -= 1\n",
    "            if cntL[x] == 1:\n",
    "                l += 1 \n",
    "            if l == r:\n",
    "                ans += 1\n",
    "            elif l > r:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        l_map = {}\n",
    "        r_map = {}\n",
    "        ans = 0\n",
    "        for i in s:\n",
    "            if(i in r_map.keys()):\n",
    "                r_map[i] += 1\n",
    "            else:\n",
    "                r_map[i] = 1\n",
    "        for i in s:\n",
    "            if(i in l_map.keys()):\n",
    "                l_map[i] += 1\n",
    "            else:\n",
    "                l_map[i] = 1\n",
    "            r_map[i] -= 1\n",
    "            if(r_map[i] == 0):\n",
    "                del r_map[i]\n",
    "            if(len(l_map) == len(r_map)):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        cnt1=collections.Counter(s)\n",
    "        cnt2=collections.Counter()\n",
    "        n=len(s)\n",
    "        ans=0\n",
    "        for i,v in enumerate(s):\n",
    "            cnt1[v]-=1\n",
    "            cnt2[v]+=1\n",
    "            if cnt1[v]==0:\n",
    "                del(cnt1[v])\n",
    "            if len(cnt1.keys())==len(cnt2.keys()):\n",
    "                ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        p, q = [0] * 26, [0] * 26\n",
    "        pcount = qcount = 0\n",
    "        res = 0\n",
    "        for c in s:\n",
    "            q[ord(c) - ord('a')] += 1\n",
    "            if q[ord(c) - ord('a')] == 1:\n",
    "                qcount += 1\n",
    "        for c in s:\n",
    "            p[ord(c) - ord('a')] += 1\n",
    "            if p[ord(c) - ord('a')] == 1:\n",
    "                pcount += 1\n",
    "            if p[ord(c) - ord('a')] == q[ord(c) - ord('a')]:\n",
    "                qcount -= 1\n",
    "            if pcount == qcount:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        p, q = [0] * 26, [0] * 26\n",
    "        pcount = qcount = 0\n",
    "        res = 0\n",
    "        for c in s:\n",
    "            q[ord(c) - ord('a')] += 1\n",
    "            if q[ord(c) - ord('a')] == 1:\n",
    "                qcount += 1\n",
    "        for c in s:\n",
    "            p[ord(c) - ord('a')] += 1\n",
    "            if p[ord(c) - ord('a')] == 1:\n",
    "                pcount += 1\n",
    "            if p[ord(c) - ord('a')] == q[ord(c) - ord('a')]:\n",
    "                qcount -= 1\n",
    "            if pcount == qcount:\n",
    "                res += 1\n",
    "            if pcount > qcount:\n",
    "                return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        pre=[0]*26\n",
    "        suf=[0]*26\n",
    "        for ch in s:\n",
    "            suf[ord(ch)-97]+=1\n",
    "        ans,p,q=0,0,sum(k>0 for k in suf)\n",
    "        for i in range(1,n):\n",
    "            pre[ord(s[i-1])-97]+=1\n",
    "            if pre[ord(s[i-1])-97]==1: p+=1\n",
    "            suf[ord(s[i-1])-97]-=1\n",
    "            if suf[ord(s[i-1])-97]==0: q-=1\n",
    "            if p==q: ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        s1_set = set()\n",
    "        s2_set = set()\n",
    "        ret = 0\n",
    "        t = len(set(s))\n",
    "        for i in range(1,length):\n",
    "            for j in s[:i]:\n",
    "                s1_set.add(j)\n",
    "                if len(s1_set) == t:\n",
    "                    break\n",
    "            for k in s[i:]:\n",
    "                s2_set.add(k)\n",
    "                if len(s2_set) == t:\n",
    "                    break\n",
    "            if len(s1_set) == len(s2_set):\n",
    "                ret+=1\n",
    "            s1_set.clear()\n",
    "            s2_set.clear()\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        mp = [26]*(len(s)-1) #mp[i]表示s[:i+1]所含有的字符数量\n",
    "        st = set()\n",
    "        for i in range(len(s)-1):\n",
    "            st.add(s[i])\n",
    "            if len(st)==26:\n",
    "                break\n",
    "            else:\n",
    "                mp[i] = len(st)\n",
    "        \n",
    "        ret = 0\n",
    "        \n",
    "        st = set()\n",
    "        for i in range(len(s)-1,0,-1):\n",
    "            st.add(s[i])\n",
    "            if mp[i-1]==len(st):\n",
    "                ret += 1\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def numSplits(self, s: str) -> int:\n",
    "    l = len(s)\n",
    "    r = [0] * l\n",
    "    t = set()\n",
    "    for i in range(l):\n",
    "      c = s[i]\n",
    "      t.add(c)\n",
    "      r[i] = len(t)\n",
    "    ret = 0\n",
    "    t = set()\n",
    "    for i in range(l - 1, 0, -1):\n",
    "      c = s[i]\n",
    "      t.add(c)\n",
    "      if len(t) == r[i - 1]:\n",
    "        ret += 1\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef numSplits(self, s: str) -> int:\n",
    "\t\ts1=set()\n",
    "\t\tsuf=[0]*len(s)\n",
    "\t\tfor i in range(len(s)-1,-1,-1):\n",
    "\t\t\ts1.add(s[i])\n",
    "\t\t\tsuf[i]=len(s1)\n",
    "\t\tans=0\n",
    "\t\ts2=set()\n",
    "\t\tfor i in range(len(s)-1):\n",
    "\t\t\ts2.add(s[i])\n",
    "\t\t\tif len(s2)==suf[i+1]:\n",
    "\t\t\t\tans+=1\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        result = 0\n",
    "        cset = set()\n",
    "        cnt = 0\n",
    "        dp = [0]*len(s)\n",
    "        for i,c in enumerate(s):\n",
    "            if(c not in cset):\n",
    "                cset.add(c)\n",
    "                cnt += 1\n",
    "            dp[i] = cnt\n",
    "        cset = set()\n",
    "        cnt = 0\n",
    "        for i in range(len(s)-2,-1,-1):\n",
    "            if(s[i+1] not in cset):\n",
    "                cset.add(s[i+1])\n",
    "                cnt += 1\n",
    "            if(dp[i] == cnt):\n",
    "                result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        total_cnt = len(set(s))\n",
    "        result = 0\n",
    "        cset = set()\n",
    "        cnt = 0\n",
    "        dp = [0]*len(s)\n",
    "        for i,c in enumerate(s):\n",
    "            if(c not in cset):\n",
    "                cset.add(c)\n",
    "                cnt += 1\n",
    "            dp[i] = cnt\n",
    "        cset = set()\n",
    "        cnt = 0\n",
    "        for i in range(len(s)-2,-1,-1):\n",
    "            if(s[i+1] not in cset):\n",
    "                cset.add(s[i+1])\n",
    "                cnt += 1\n",
    "            if(dp[i] == cnt):\n",
    "                result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        # 遍历统计正向到每个坐标的不同字符的数量\n",
    "        nums = [0]\n",
    "        now, lst = 0, set()\n",
    "        for ch in s:\n",
    "            if ch not in lst:\n",
    "                lst.add(ch)\n",
    "                now += 1\n",
    "            nums.append(now)\n",
    "        nums.pop()\n",
    "\n",
    "        # 反向遍历每个坐标的不同字符数量与正向是否相同\n",
    "        ans = 0\n",
    "        now, lst = 0, set()\n",
    "        for ch in s[::-1]:\n",
    "            if ch not in lst:\n",
    "                lst.add(ch)\n",
    "                now += 1\n",
    "            if nums.pop() == now:\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = [0] * (n + 2), [0] * (n + 2)\n",
    "\n",
    "        rec_left = [False] * 26\n",
    "        rec_right = [False] * 26\n",
    "        for i in range(1, n + 1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if rec_left[c]:\n",
    "                left[i] = left[i - 1]\n",
    "            else:\n",
    "                rec_left[c] = True\n",
    "                left[i] = left[i - 1] + 1\n",
    "        \n",
    "        for i in range(n, 0, -1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if (rec_right[c]):\n",
    "                right[i] = right[i + 1]\n",
    "            else:\n",
    "                rec_right[c] = True\n",
    "                right[i] = right[i + 1] + 1\n",
    "        \n",
    "        ret = sum(1 for i in range(1, n) if left[i] == right[i + 1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = [0] * (n + 2), [0] * (n + 2)\n",
    "\n",
    "        rec_left = [False] * 26\n",
    "        rec_right = [False] * 26\n",
    "        for i in range(1, n + 1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if rec_left[c]:\n",
    "                left[i] = left[i - 1]\n",
    "            else:\n",
    "                rec_left[c] = True\n",
    "                left[i] = left[i - 1] + 1\n",
    "        \n",
    "        for i in range(n, 0, -1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if (rec_right[c]):\n",
    "                right[i] = right[i + 1]\n",
    "            else:\n",
    "                rec_right[c] = True\n",
    "                right[i] = right[i + 1] + 1\n",
    "        \n",
    "        ret = sum(1 for i in range(1, n) if left[i] == right[i + 1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # res = 0\n",
    "        # for i in range(1, n):\n",
    "        #     s1 = len(set(s[:i]))\n",
    "        #     s2 = len(set(s[i:]))\n",
    "        #     if s1 == s2:\n",
    "        #         res += 1\n",
    "        # return res\n",
    "        left = [0] * (n + 2)\n",
    "        right = [0] * (n + 2)\n",
    "        rec_left = [False] * 26\n",
    "        rec_right = [False] * 26\n",
    "        for i in range(1, n+1):\n",
    "            c = ord(s[i-1]) - ord(\"a\")\n",
    "            if rec_left[c]:\n",
    "                left[i] = left[i-1]\n",
    "            else:\n",
    "                rec_left[c] = True\n",
    "                left[i] = left[i-1] + 1\n",
    "        \n",
    "        for i in range(n, 0, -1):\n",
    "            c = ord(s[i-1]) - ord(\"a\")\n",
    "            if rec_right[c]:\n",
    "                right[i] = right[i+1]\n",
    "            else:\n",
    "                rec_right[c] = True\n",
    "                right[i] = right[i+1] + 1\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            if left[i] == right[i+1]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def numSplits(self, s: str) -> int:\n",
    "#         def counts(x):\n",
    "#             tmp = 0\n",
    "#             while x:\n",
    "#                 if x&1 == 1:\n",
    "#                     tmp += 1\n",
    "#                 x >>= 1\n",
    "#             return tmp\n",
    "        \n",
    "#         n = len(s)\n",
    "#         statsl ,statsr = [0] * (n + 1), [0] * (n + 1)\n",
    "#         statsl[0] =  (1 << (ord(s[0]) - ord('a')))\n",
    "#         for i in range(1, n):\n",
    "#             statsl[i] = statsl[i-1] | (1 << (ord(s[i]) - ord('a')))\n",
    "#             statsr[n - i - 1] = statsr[n - i] | (1 << (ord(s[n - i]) - ord('a')))\n",
    "#         ans = 0\n",
    "#         for i in range(n-1):\n",
    "#             if counts(statsl[i]) == counts(statsr[i]):\n",
    "#                 ans += 1\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = [0] * (n + 2), [0] * (n + 2)\n",
    "\n",
    "        rec_left = [False] * 26\n",
    "        rec_right = [False] * 26\n",
    "        for i in range(1, n + 1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if rec_left[c]:\n",
    "                left[i] = left[i - 1]\n",
    "            else:\n",
    "                rec_left[c] = True\n",
    "                left[i] = left[i - 1] + 1\n",
    "        \n",
    "        for i in range(n, 0, -1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if (rec_right[c]):\n",
    "                right[i] = right[i + 1]\n",
    "            else:\n",
    "                rec_right[c] = True\n",
    "                right[i] = right[i + 1] + 1\n",
    "        \n",
    "        ret = sum(1 for i in range(1, n) if left[i] == right[i + 1])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = [0] * (n + 2), [0] * (n + 2)\n",
    "\n",
    "        rec_left = [False] * 26\n",
    "        rec_right = [False] * 26\n",
    "        for i in range(1, n + 1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if rec_left[c]:\n",
    "                left[i] = left[i - 1]\n",
    "            else:\n",
    "                rec_left[c] = True\n",
    "                left[i] = left[i - 1] + 1\n",
    "        \n",
    "        for i in range(n, 0, -1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if (rec_right[c]):\n",
    "                right[i] = right[i + 1]\n",
    "            else:\n",
    "                rec_right[c] = True\n",
    "                right[i] = right[i + 1] + 1\n",
    "        \n",
    "        ret = sum(1 for i in range(1, n) if left[i] == right[i + 1])\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = [0] * (n + 2), [0] * (n + 2)\n",
    "\n",
    "        rec_left = [False] * 126\n",
    "        rec_right = [False] * 126\n",
    "        for i in range(1, n + 1):\n",
    "            c = ord(s[i - 1]) \n",
    "            if rec_left[c]:\n",
    "                left[i] = left[i - 1]\n",
    "            else:\n",
    "                rec_left[c] = True\n",
    "                left[i] = left[i - 1] + 1\n",
    "        \n",
    "        for i in range(n, 0, -1):\n",
    "            c = ord(s[i - 1]) \n",
    "            if (rec_right[c]):\n",
    "                right[i] = right[i + 1]\n",
    "            else:\n",
    "                rec_right[c] = True\n",
    "                right[i] = right[i + 1] + 1\n",
    "        \n",
    "        return  sum(1 for i in range(1, n) if left[i] == right[i + 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = [0] * (n + 2), [0] * (n + 2)\n",
    "\n",
    "        rec_left = [False] * 126\n",
    "        rec_right = [False] * 126\n",
    "        for i in range(1, n + 1):\n",
    "            c = ord(s[i - 1]) \n",
    "            if rec_left[c]:\n",
    "                left[i] = left[i - 1]\n",
    "            else:\n",
    "                rec_left[c] = True\n",
    "                left[i] = left[i - 1] + 1\n",
    "        \n",
    "        for i in range(n, 0, -1):\n",
    "            c = ord(s[i - 1]) \n",
    "            if (rec_right[c]):\n",
    "                right[i] = right[i + 1]\n",
    "            else:\n",
    "                rec_right[c] = True\n",
    "                right[i] = right[i + 1] + 1\n",
    "        \n",
    "        return  sum(1 for i in range(1, n) if left[i] == right[i + 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pre = [0]*(n+1)\n",
    "        dct = set()\n",
    "        for i in range(n):\n",
    "            dct.add(s[i])\n",
    "            pre[i+1] = len(dct)\n",
    "\n",
    "        post = [0] * (n + 1)\n",
    "        dct = set()\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dct.add(s[i])\n",
    "            post[i] = len(dct)\n",
    "        \n",
    "        return sum(pre[i+1]==post[i+1] for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = [0] * (n + 2), [0] * (n + 2)\n",
    "\n",
    "        rec_left = [False] * 26\n",
    "        rec_right = [False] * 26\n",
    "        for i in range(1, n + 1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if rec_left[c]:\n",
    "                left[i] = left[i - 1]\n",
    "            else:\n",
    "                rec_left[c] = True\n",
    "                left[i] = left[i - 1] + 1\n",
    "        \n",
    "        for i in range(n, 0, -1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if (rec_right[c]):\n",
    "                right[i] = right[i + 1]\n",
    "            else:\n",
    "                rec_right[c] = True\n",
    "                right[i] = right[i + 1] + 1\n",
    "        \n",
    "        ret = sum(1 for i in range(1, n) if left[i] == right[i + 1])\n",
    "        return ret\n",
    "\n",
    "\n",
    "        # dict1 = defaultdict(int)\n",
    "        # en_set_r = set()\n",
    "        # en_set_l = set()\n",
    "        # for i in s:\n",
    "        #     if dict1[i] == 0:\n",
    "        #         en_set_r.add(i)\n",
    "        #     dict1[i] += 1\n",
    "        # res = 0\n",
    "        # for i in s:\n",
    "        #     dict1[i] -= 1\n",
    "        #     if i not in en_set_l:\n",
    "        #         en_set_l.add(i)\n",
    "        #     if dict1[i] == 0:\n",
    "        #         en_set_r.remove(i)\n",
    "        #     if len(en_set_l) == len(en_set_r):\n",
    "        #         res += 1\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = [0] * (n + 1), [0] * (n + 1)\n",
    "\n",
    "        rec_left = [False] * 26\n",
    "        rec_right = [False] * 26\n",
    "        for i in range(1, n + 1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if rec_left[c]:\n",
    "                left[i] = left[i - 1]\n",
    "            else:\n",
    "                rec_left[c] = True\n",
    "                left[i] = left[i - 1] + 1\n",
    "        \n",
    "        for i in range(n, 0, -1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if (rec_right[c]):\n",
    "                right[i - 1] = right[i]\n",
    "            else:\n",
    "                rec_right[c] = True\n",
    "                right[i - 1] = right[i] + 1\n",
    "        \n",
    "        ret = sum(1 for i in range(1, n) if left[i] == right[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        pre = [0]*(len(s)-1)\n",
    "        rev = [0]*(len(s)-1)\n",
    "        pre_map = set()\n",
    "        for i in range(len(s)-1):\n",
    "            if s[i] not in pre_map:\n",
    "                pre_map.add(s[i])\n",
    "                pre[i] = len(pre_map)\n",
    "            else:\n",
    "                pre[i] = len(pre_map)\n",
    "\n",
    "        pre_map = set()\n",
    "        for i in range(len(s)-1,0,-1):\n",
    "            if s[i] not in pre_map:\n",
    "                pre_map.add(s[i])\n",
    "                rev[i-1] = len(pre_map)\n",
    "            else:\n",
    "                rev[i-1] = len(pre_map)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(len(pre)):\n",
    "            if pre[i] == rev[i]:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = [0] * (n + 2), [0] * (n + 2)\n",
    "\n",
    "        rec_left = [False] * 26\n",
    "        rec_right = [False] * 26\n",
    "        for i in range(1, n + 1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if rec_left[c]:\n",
    "                left[i] = left[i - 1]\n",
    "            else:\n",
    "                rec_left[c] = True\n",
    "                left[i] = left[i - 1] + 1\n",
    "        \n",
    "        for i in range(n, 0, -1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if (rec_right[c]):\n",
    "                right[i] = right[i + 1]\n",
    "            else:\n",
    "                rec_right[c] = True\n",
    "                right[i] = right[i + 1] + 1\n",
    "        \n",
    "        ret = sum(1 for i in range(1, n) if left[i] == right[i + 1])\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = [0] * (n + 2), [0] * (n + 2)\n",
    "\n",
    "        rec_left = [False] * 26\n",
    "        rec_right = [False] * 26\n",
    "        for i in range(1, n + 1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if rec_left[c]:\n",
    "                left[i] = left[i - 1]\n",
    "            else:\n",
    "                rec_left[c] = True\n",
    "                left[i] = left[i - 1] + 1\n",
    "        \n",
    "        for i in range(n, 0, -1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if (rec_right[c]):\n",
    "                right[i] = right[i + 1]\n",
    "            else:\n",
    "                rec_right[c] = True\n",
    "                right[i] = right[i + 1] + 1\n",
    "        \n",
    "        ret = sum(1 for i in range(1, n) if left[i] == right[i + 1])\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = [0] * (n + 2), [0] * (n + 2)\n",
    "\n",
    "        rec_left = [False] * 26\n",
    "        rec_right = [False] * 26\n",
    "        for i in range(1, n + 1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if rec_left[c]:\n",
    "                left[i] = left[i - 1]\n",
    "            else:\n",
    "                rec_left[c] = True\n",
    "                left[i] = left[i - 1] + 1\n",
    "        \n",
    "        for i in range(n, 0, -1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if (rec_right[c]):\n",
    "                right[i] = right[i + 1]\n",
    "            else:\n",
    "                rec_right[c] = True\n",
    "                right[i] = right[i + 1] + 1\n",
    "        \n",
    "        ret = sum(1 for i in range(1, n) if left[i] == right[i + 1])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = [0] * (n + 2), [0] * (n + 2)\n",
    "\n",
    "        rec_left = [False] * 26\n",
    "        rec_right = [False] * 26\n",
    "        for i in range(1, n + 1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if rec_left[c]:\n",
    "                left[i] = left[i - 1]\n",
    "            else:\n",
    "                rec_left[c] = True\n",
    "                left[i] = left[i - 1] + 1\n",
    "        \n",
    "        for i in range(n, 0, -1):\n",
    "            c = ord(s[i - 1]) - ord(\"a\")\n",
    "            if (rec_right[c]):\n",
    "                right[i] = right[i + 1]\n",
    "            else:\n",
    "                rec_right[c] = True\n",
    "                right[i] = right[i + 1] + 1\n",
    "        \n",
    "        ret = sum(1 for i in range(1, n) if left[i] == right[i + 1])\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pre = [0] * n\n",
    "        suf = [0] * n\n",
    "        dictp = {s[0]:1}\n",
    "        dicts = {s[n - 1]:1}\n",
    "        for i in range(1, n):\n",
    "            pre[i] = pre[i - 1]\n",
    "            suf[n - 1 - i] = suf[n - i]\n",
    "            if s[i] not in dictp:\n",
    "                dictp[s[i]] = 1\n",
    "                pre[i] += 1\n",
    "            if s[n - 1 - i] not in dicts:\n",
    "                dicts[s[n - 1 - i]] = 1\n",
    "                suf[n - 1 - i] += 1\n",
    "        res = 0\n",
    "        #print(pre)\n",
    "        #print(suf)\n",
    "        for i in range(n - 1):\n",
    "            if pre[i] == suf[i + 1]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = [0 for _ in range(n)], [0 for _ in range(n)]\n",
    "        cnt = set()\n",
    "        for i, x in enumerate(s):\n",
    "            cnt.add(x)\n",
    "            left[i] = len(cnt)\n",
    "        cnt = set()\n",
    "        for i in range(n-1, -1, -1):\n",
    "            cnt.add(s[i])\n",
    "            right[i] = len(cnt)\n",
    "        ans = 0\n",
    "        for i in range(0, n-1):\n",
    "            if left[i] == right[i+1]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pre = [0 for _ in range(n)]\n",
    "        suf = [0 for _ in range(n)]\n",
    "        pre_set = set()\n",
    "        suf_set = set()\n",
    "        for i in range(n):\n",
    "            pre_set.add(s[i])\n",
    "            suf_set.add(s[n - i - 1])\n",
    "            pre[i] = len(pre_set)\n",
    "            suf[n - i - 1] = len(suf_set)\n",
    "        ret = 0\n",
    "        for i in range(1, n):\n",
    "            if pre[i - 1] == suf[i]:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        stackA = []\n",
    "        visited = set()\n",
    "        for ch in s:\n",
    "            visited.add(ch)\n",
    "            stackA.append(len(visited))\n",
    "        m = len(visited)\n",
    "        if m == 1:\n",
    "            return len(s) - 1\n",
    "        stackB = []\n",
    "        visited = set()\n",
    "        for ch in s[::-1]:\n",
    "            visited.add(ch)\n",
    "            stackB.append(len(visited))\n",
    "        ans = 0\n",
    "        stackB = stackB[::-1]\n",
    "        print(stackA, stackB)\n",
    "        for i in range(len(s)-1):\n",
    "            if stackA[i] == stackB[i+1]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSplits(self, s: str) -> int:\n",
    "        stackA = []\n",
    "        visited = set()\n",
    "        for ch in s:\n",
    "            visited.add(ch)\n",
    "            stackA.append(len(visited))\n",
    "        m = len(visited)\n",
    "        if m == 1:\n",
    "            return len(s) - 1\n",
    "        stackB = []\n",
    "        visited = set()\n",
    "        for ch in s[::-1]:\n",
    "            visited.add(ch)\n",
    "            stackB.append(len(visited))\n",
    "        ans = 0\n",
    "        stackB = stackB[::-1]\n",
    "\n",
    "        for i in range(len(s)-1):\n",
    "            if stackA[i] == stackB[i+1]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
